package xio.leetcode.java;

import java.util.Arrays;

/**
 * 88. Merge Sorted Array (Easy)
 * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
 *
 * 说明:
 *
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
 * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 * 示例:
 *
 * 输入:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 *
 * 输出: [1,2,2,3,5,6]
 *
 * 思路：双指针遍历，两个都从尾开始遍历；
 */
public class LC88_Merge {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n;
        while (i>=0 && j>=0){
            int r1 = nums1[i];
            int r2 = nums2[j];
            if (r1 > r2){
                nums1[--k] = r1;
                i--;
            }else if (r1 < r2){
                nums1[--k] = r2;
                j--;
            }else{
                nums1[--k] = r1;
                nums1[--k] = r2;
                i--;
                j--;
            }
        }
        // 因为上面while的判断条件是i和j都大于0，因此执行到这儿，可能存在有i或j其中一个大于0，即num1或者num2没有遍历完的情况，应该把没有遍历完的元素放到num1的前面。
        // 因为最终结果是合并到num1上，因此如果是num1没有遍历完可以不管，只需要处理num2的结果
        while (j>=0){
            nums1[j] = nums2[j];
            j--;
        }
    }

    public static void main(String[] args) {
        int[] num1 = new int[]{4,5,6,0,0,0};
        int[] num2 = new int[]{1,2,3};
        LC88_Merge me = new LC88_Merge();
        me.merge(num1,3,num2,num2.length);
        System.out.println(Arrays.toString(num1));
    }
}
